The invention generally relates to data recovery systems, and relates in particular to data recovery systems for NAND gate array memories.
NAND gate array memories are a popular technology used in flash memories due, in part, to their low cost and high density (up to 16 Gb per chip). The technology has been used widely in handheld devices such as USB drives, cell phones, touch phones, iPod™ devices and iPhones™ devices sold by Apple, Inc. of Cupertino, Calif., etc. Further future computing devices such as laptops may also include such memory devices. Users store important information on these storage devices such as emails, photos, financial information, and personal data.
Device failures, however, such as hardware faults, OS failures, physical damages, virus attacks, and user errors sometimes occur resulting in data damages or data losses. Moreover, the charge stored in each floating gate of each transistor in a NAND gate array memory will leak in time, and blocks within each NAND gate array memory sometimes become damaged during use (e.g., during writing and erasing operations). For these reasons, NAND gate array memories are typically provided with spare memory area such that a bad block may be labeled as such, and data may instead be diverted to good blocks within the NAND gate array memory. More importantly, each block in an NAND gate array flash has limited number of erase cycles (10,000 for MLC and 100,000 for SLC). A process called wear leveling is typically employed to spread the use of data blocks as uniformly as possible to provide that the blocks wear out more evenly. When transistors and blocks become damaged, however, data therein will be lost. There is a need, therefore, for techniques to recover data from such NAND gate array memories in case of failures. Furthermore, there is also a need in computer forensics to recover data evidence from such handheld devices in case of physical damages or files having been deleted.
Handheld devices are typically not as well protected as traditional storages such as disks, which may be maintained in air-conditioned data centers and may be managed by information technology (IT) professionals. Mature data protection technologies such as traditional backup, snapshot techniques, continuous data protection (CDP), timely recovery to any point-in-time (TRAP) array, and Coupling Update by Parities (CUP) data technologies are available to protect data stored in hard disk drives and data can be recovered in case of failures. Handheld devices are used by the general public, and as a result, failures such as hardware faults, physical damages, and user errors occur more frequently than with hard disks that are maintained by IT professionals. In addition, majority of users do not do backup or snapshot for data stored on these handheld devices. Recovering data from such NAND gate array memories presents significant technical challenges.
U.S. Published Patent Application Publication No. 2008/0104308, for example, discloses a technique to rebuild the block mapping table for the purpose of providing a quick reboot from flash memory in the event that the mapping table is lost in the RAM memory. During rebooting, the latest updated wear-sorted block list (WSBL) is read from non-volatile cache memory, and then the block mapping data is restored with reference to erasing counts for the blocks. The system does not, however, provide for the recovery of data stored in a flash memory to a previous point in time.
U.S. Pat. No. 6,970,890 discloses a method of using base block copies to define the location of selected data structures used for file system management. The method uses at least two of the base block copies to provide redundancy so that in the event one of the copies cannot be located or verified, the other copy can be used to rebuild the defective base block copy. This scheme, however, requires modification of file systems to provide redundancy.
In an article titled Forensic Data Recovery From Flash Memory, by M. Breeuwsma, de Jongh, Martien, Klayer, Coert, van der Knijff, Ronald, Roeloffs, Mark, Small Scale Digital Device Forensics Journal, vol. 1, no. 1 (June 2007), it is disclosed that three low-level data acquisition methods may be employed for making full memory copies of flash memory devices. Steps are also disclosed therein for translating the extracted data into a format that may be understood by common forensic media analysis tools. The systems of this article, however, do not make the raw data readable by upper layer file systems, and further are not able to recover data to a previous point in time by tracing the block logs that exist in NAND gate array memories and are invisible to file systems or users.
There remains a need therefore, for a data recovery system for flash memory storage that is able to recover data to a previous point in time in case of failures.